<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
      这是一道很明显的后序遍历的题，判断每个节点的最大值，然后回溯
      每个节点可偷的最大值为：Math.max(root.left.val+root.right.val,root.val)
      */
      let tree = {
        val: 3,
        left: {
          val: 2,
          right: {
            val: 3
          }
        },
        right: {
          val: 3,
          right: {
            val: 1
          }
        }
      }
      //如果这种写法就是我们每次挑的都是当前的最大值，但是没法跳过去挑。因为挑了子节点导致当前节点选不到。因此只能用数组
      var rob = function (root) {
        let res = 0
        function postOrder(root) {
          if (!root) return [0, 0] //left[0]表示不偷左子节点的最大值，left[1]表示偷左子节点的最大值
          let left = postOrder(root.left)
          let right = postOrder(root.right)
          let withRoot = left[0] + right[0] + root.val
          //如果不偷当前节点，左右子节点可偷可不偷
          let outRoot = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
          return [outRoot, withRoot]
        }
        let arr = postOrder(root)
        return Math.max(...arr)
      }
      rob(tree)
    </script>
  </body>
</html>
